package com.kabuda.zhugehot200_review;

/**
 * @author kabuda
 * @date 2025-03-15 14:37
 * @description 统计n以内的素数的个数
 */
public class t204_素数个数统计 {


    public static void main(String[] args) {
        System.out.println(countPrimes(5));
    }


    /**
     * 埃筛法:要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
     * @param n
     * @return
     */
    public static int countPrimes(int n) {
        //false代表不是质数
        boolean[] isPrime = new boolean[n];
        int result=0;
        //已知0,1不是质数
        for (int i = 2; i < n; i++) {
            //第一个n是2,已知是质数
            if(!isPrime[i]){
                //如果是质数就进来
                result++;
                //质数*质数=合数
                //合数+质数=合数
                for (int j =i*i ; j < n; j+=i) {
                    isPrime[j]=true;
                }
            }
        }
        return result;
    }



}
